package pers.sloera.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 每日温度
 *
 * @author sloera
 * @date 2022-07-24 19:38:05
 */
class DailyTemperatures {
    public static void main(String[] args) {
        Solution solution = new DailyTemperatures().new Solution();
        int[] ints = solution.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73});
        System.out.println(ints);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            // 存储未找到的索引
            Deque<Integer> deque = new LinkedList<>();
            //  下一个更高温度的几天后天数
            int[] result = new int[temperatures.length];
            Arrays.fill(result, 0);
            for (int i = 0; i < temperatures.length; i++) {
                while (!deque.isEmpty() && temperatures[i] > temperatures[deque.peek()]) {
                    Integer lastIndex = deque.pop();
                    result[lastIndex] = i - lastIndex;
                }
                deque.push(i);
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
